Идея проверки совместимости дуг легла в основу быстрого метода распространения ограничений, который является значительно более мощным по сравнению с предварительной проверкой. В данном случае термин дуга обозначает ориентированное ребро в графе ограничений, такое как дуга от SA до NSW. Если рассматриваются текущие области определения SA и NSW, то дуга является совместимой, если для каждого значения х переменной SA существует некоторое значение у переменной NSW, которое совместимо с х. В третьей строке на рис. 5.4 текущими областями определения SA и NSW являются {blue} и {red, blue} соответственно. При SA=blue существует совместимое присваивание для NSW, а именно NSW=red, поэтому дуга от SA до NSW совместима. С другой стороны, обратная дуга от NSWjxo SA несовместима, поскольку применительно к присваиванию NSW=blue не существует совместимого присваивания для SA. Эту дугу можно сделать совместимой, удалив значение blue из области определения NSW.

На том же этапе в процессе поиска проверку совместимости дуг можно также применить к дуге от SA до NT. Третья строка таблицы, приведенной на рис. 5.4, показывает, что обе переменные имеют область определения {blue}. Результатом становится то, что значение blue должно быть удалено из области определения SA, после чего эта область определения остается пустой. Таким образом, применение проверки совместимости дуг привело к раннему обнаружению той несовместимости, которая не была обнаружена с помощью предварительной проверки, применяемой в чистом виде.

Проверку совместимости дуг можно использовать либо в качестве этапа предварительной обработки перед началом процесса поиска, либо в качестве этапа распространения ограничения (аналогично предварительной проверке) после каждого присваивания во время поиска. (Последний алгоритм иногда называют MAC, сокращенно обозначая метод поддержки совместимости дуг— Maintaining Arc Consistency.) И в том и в другом случае процесс проверки необходимо выполнять повторно, до тех пор, пока не перестанут обнаруживаться какие-либо несовместимости. Это связано с тем, что при удалении (в целях устранения некоторой несовместимости дуг) любого значения из области определения некоторой переменной может появиться новая несовместимость дуг в тех дугах, которые указывают на эту переменную. В полном алгоритме проверки совместимости дуг, АС-3, используется очередь для отслеживания дуг, которые должны быть проверены на несовместимость (листинг 5.2). Каждая дугапо очереди "снимается с повестки дня" и проверяется; если из области определения xi необходимо удалить какие-либо значения, то каждая дуга, указывающая на хi, должна быть повторно вставлена в очередь для проверки. Сложность проверки совместимости дуг можно проанализировать следующим образом: любая бинарная задача CSP имеет самое большее дуг; каждая дуга может быть "внесена в повестку дня" только d раз, поскольку область определения xi имеет самое большее d значений, доступных для удаления; проверка совместимости любой дуги может быть выполнена за время , поэтому в наихудшем случае затраты времени составляют . Хотя такой метод является значительно более дорогостоящим по сравнению с предварительной проверкой, все эти дополнительные затраты обычно окупаются.